package woa.binarysearch;

import java.util.*;

/**
 * 两个数组的交集
 * 给定两个数组，编写一个函数来计算它们的交集。
 *
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2]
 *
 * @author wangpeng
 * @date 2021/12/22
 */
public class Intersection {

    public static int[] intersection(int[] nums1, int[] nums2) {
        List<Integer> list = new ArrayList<>();
        int len1 = nums1.length, len2 = nums2.length;
        int[] sotred = null;
        if (len1 > len2) {
            Arrays.sort(nums1);
            sotred = nums1;
        } else {
            Arrays.sort(nums2);
            sotred = nums2;
        }
        int[] target = len1 > len2 ? nums2 : nums1;
        Set<Integer> cache = new HashSet<>(8);
        for (int i = 0; i < target.length; i++) {
            if (cache.contains(target[i])) {
                continue;
            }
            int idx = Arrays.binarySearch(sotred, target[i]);
            if (idx > -1) {
                list.add(target[i]);
            }
            cache.add(target[i]);
        }
        int[] rs = new int[list.size()];
        for (int i = 0; i < rs.length; i++) {
            rs[i] = list.get(i);
        }
        return rs;
    }


    public static void main(String[] args) {
        System.out.println(Arrays.toString(intersection(new int[]{4,9,5}, new int[]{9,4,9,8,4})));
    }

}
